package datastructure.tree;


//二叉树代码
public class BinaryTree<Key extends Comparable<Key>,Value> {
    private class Node{
        public Key key;
        private Value value;
        public Node left;
        public Node right;
        public Node(Key key,Value value,Node left,Node right){
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    private Node root;
    private int N;
    //获取树中元素的个数
    public int size(){
        return N;
    }

    //向树中添加元素key-value
    public void put(Key key,Value value){
        root  = put(root,key,value);
    }

    //向指定的树(其实就是指定的节点)中添加元素，并返回新生成的树（节点），因为在类中有上一个重载方法，调用的时候其实是调用上一个方法
    //每次向树中添加元素其实还是从root节点开始尝试插入,所以上行代码是  root  = put(root,key,value);
    public Node put(Node x,Key key,Value value){
        //向指定树插入的时候，也分情况两种情况
        //一、指定的树为空，
        if(x == null){
            N ++;
            return new Node(key,value,null,null);
        }
        //二、指定的树不为空
        int cmp = key.compareTo(x.key);
        if(cmp>0){
            x.right = put(x.right,key,value);
        }else if(cmp<0){
            x.left = put(x.left,key,value);
        }else {
            x.value = value;
        }
        return x;

    }
}
